import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 剑指 Offer 59 - II. 队列的最大值
 * https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
 */
public class Solutions_Offer_59 {
    public static void main(String[] args) {
        MaxQueue obj = new MaxQueue();
        obj.push_back(4);
        obj.push_back(2);
        int res1 = obj.max_value();  // output: 4
        System.out.println(res1);
        int res2 = obj.pop_front();  // output: 4
        System.out.println(res2);
        int res3 = obj.max_value();  // output: 2
        System.out.println(res3);
        obj.push_back(0);
        obj.push_back(3);
        int res4 = obj.max_value();  // output: 3
        System.out.println(res4);
    }
}

class MaxQueue {
    private Deque<Integer> queue;  // 存储入队的元素
    private Deque<Integer> maxValues;  // 存储单调递减的元素

    public MaxQueue() {
        queue = new ArrayDeque<>();
        maxValues = new ArrayDeque<>();
    }

    public int max_value() {
        // 最大值
        return maxValues.isEmpty() ? -1 : maxValues.peek();
    }

    public void push_back(int value) {
        // 元素入队
        // 关键点：maxValues 中，当一个元素进入队列的时候，队列之前的所有比它小的元素就不会再对答案产生影响。
        // 例如：2, 0, 3, 1，当 3 入队时，之前添加的比 3 小的 2 与 0 都出队，因为对于后面的 1 来说，队列中的最大值就只是 3
        queue.offer(value);
        while (!maxValues.isEmpty() && value > maxValues.peekLast()) {
            // 将 value 与 maxValues 队列尾部 的元素依次比较，将小于 value 的元素都进行出队操作
            maxValues.pollLast();
        }
        maxValues.offer(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        // 元素出队
        int val = queue.poll();
        if (val == maxValues.peek()) {
            // 判断出队的元素是否是当前队列中的最大值，即 maxValues 的队首元素
            // 若是，最大值也需要出队
            maxValues.poll();
        }
        return val;
    }
}